//117.填充每个节点的下一个右侧节点指针Ⅱ
//https://leetcode.cn/problems/populating-next-right-pointers-in-each-node-ii
class Solution {
public:
    Node* connect(Node* root) {
        if(!root) return root;

        queue<Node*> q;
        q.push(root);
        Node* prev = nullptr;
        while(!q.empty())
        {
            prev = nullptr;
            int n = q.size();
            while(n--)
            {
                Node* nd = q.front(); q.pop();
                if(nd->left) q.push(nd->left);
                if(nd->right) q.push(nd->right);
                if(prev) prev->next = nd;
                prev = nd;
            }
        }
        return root;
    }
};